package com.fufu.algorithem.stack;

/**
 * 利用栈实现个位数的add、sub、mul、div
 * @author: BlcakTiger
 * @date: 2023/2/12 12:35
 * @contact: hsf6661@163.com
 */
public class Calculator1 {

    public static void main(String[] args) {
        Calculator1 calc = new Calculator1();
        //表达式
        String expression = "10*((10*6)-2)";
        //用于遍历表达式的索引
        int index = 0;
        //用于接收表达式的每个字符
        char ch = ' ';
        //用于计算
        int num1 = 0;
        int num2 = 0;
        //用于拼接多位数
        String numCat = "";
        //遍历表达式
        while (index < expression.length()){
            //获取表达式字符
            ch = expression.substring(index,index+1).charAt(0);
            //判断当前字符是否是操作符
            if (calc.isOperator(ch)){
                //判断符号栈是否为null
                if (calc.operatorStack.isEmpty()){
                    calc.operatorStack.push(ch);
                }else {
                    //如果当前操作符的优先级大于当前符号栈栈顶的操作符，直接入栈；
                    //如果小于，则需要先将之前优先级较高的运算符进行运算，具体操作为：从数栈pop出2个数，从符号栈pop出1个操作符
                    //将计算结果再重新入数栈，并将当前操作符入符号栈
                    if (calc.priority(ch) > calc.priority((char)calc.operatorStack.peek())){
                        calc.operatorStack.push(ch);
                    }else {
                        num1 = Integer.parseInt(calc.numStack.pop().toString());
                        num2 = Integer.parseInt(calc.numStack.pop().toString());
                        char opeartor = (char)calc.operatorStack.pop();
                        calc.numStack.push(calc.numCalc(num2,num1,opeartor));
                        calc.operatorStack.push(ch);
                    }
                }
            }else{//执行到这里，说明字符是数字，此时，不能直接将字符入数栈
                numCat += ch;
                //当index等于字符串的最后一位，直接将numCat入数栈
                if (index==expression.length()-1){
                    calc.numStack.push(numCat);
                }else{
                    //判断当前字符的后一位是否还是数字，如果是，将其拼接起来
                    if (calc.isOperator(expression.substring(index+1,index+2).charAt(0))){
                        calc.numStack.push(numCat);
                        numCat = "";
                    }
                }
            }
            index++;
        }
        //走到这一步，符号栈中剩下的符号优先级都是相等的，直接按顺序计算即可，当符号栈为空时，表明计算完毕,此时数栈剩下唯一一个元素即是结果
        while (true){
            if (calc.operatorStack.isEmpty()){
                break;
            }
            num1 = Integer.parseInt(calc.numStack.pop()+"");
            num2 = Integer.parseInt(calc.numStack.pop().toString());
            char opeartor = (char)calc.operatorStack.pop();
            calc.numStack.push(calc.numCalc(num2,num1,opeartor));
        }
        System.out.println("计算结果："+calc.numStack.peek());


    }

    /**
     * 定义一个数stack存放数字
     */
    private StackByLinkedList numStack;
    /**
     * 定义一个符号栈用于存放运算符
     */
    private StackByLinkedList operatorStack;

    //定义优先级
    private final int ADD_OPER = 1;
    private final int SUB_OPER = 1;
    private final int MUL_OPER = 2;
    private final int DIV_OPER = 2;

    /**
     * 构造方法，初始化一些参数
     */
    public Calculator1(){
        numStack = new StackByLinkedList();
        operatorStack = new StackByLinkedList();
    }

    /**
     * 判断传入的字符是否是一个操作符
     * @param ch 需要判断的字符
     * @return 是操作符，返回true，否则返回false
     */
    public boolean isOperator(char ch){
        return ch=='+' || ch=='-' || ch=='*' || ch=='/';
    }

    /**
     * 返回操作符的优先级
     * @param operator 操作符
     * @return 返回-1表示操作符类型错误
     */
    public int priority(char operator){
        switch (operator){
            case '+':
                return ADD_OPER;
            case '-':
                return SUB_OPER;
            case '*':
                return MUL_OPER;
            case '/':
                return DIV_OPER;
            default:
                return -1;
        }
    }

    /**
     * 根据操作符计算两个数的运算
     * @param num1 操作数1
     * @param num2 操作数2
     * @param operator 操作符
     * @return 若返回-1，表明操作符类型错误
     */
    public int numCalc(int num1,int num2,char operator){
        switch (operator){
            case '+':
                return num1+num2;
            case '-':
                return num1-num2;
            case '*':
                return num1*num2;
            case '/':
                return num1/num2;
            default:
                return -1;
        }
    }
}

/**
 * 创建一个链表
 */
class StackByLinkedList {

    /**
     * 头节点
     */
    private Node head;

    /**
     * 入栈
     * @param o 入栈的节点
     */
    public void push(Object o){
        if (head==null){
            head = new Node(o);
        }else {
            Node node = new Node(o);
            node.next = head;
            head = node;
        }
    }

    /**
     * 出栈
     */
    public Object pop(){
        if (head==null){
            throw new RuntimeException("Stack is empty!");
        }
        Node temp = head;
        head = head.next;
        return temp.data;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return head == null;
    }

    /**
     * 返回栈顶元素
     * @return
     */
    public Object peek(){
        return head.data;
    }

    /**
     * 遍历
     */
    public void iterator(){
        if (head==null){
            throw new RuntimeException("Stack is empty!");
        }
        Node temp = head;
        System.out.print("[");
        while (temp!=null){
            System.out.print(temp.data+" ");
            temp=temp.next;
        }
        System.out.println("]");
    }
}

/**
 * 节点类
 */
class Node{
    /**
     * 数据域
     * 用于保存节点中的数据
     */
    Object data;
    /**
     * next域
     * 用于存放当前节点的下一个节点
     */
    Node next;

    public Node(Object data){
        this.data = data;
    }
}

